package com.cheng.dataStructure.linkedlist;

/**
 * @User Administrator
 * @Classname Josephus
 * @Project Data-structure-and-algorithm
 * @Description 约瑟夫问题（约瑟夫环）分析以及代码实现
 * 约瑟夫问题：假设n个小孩围坐一圈，约定编号为k(1<=k<=n)的小孩开始报数，数到m的那个人出圈，出圈人的下一位又开始从1报数，数到m的那个人又出圈，
 * 以此类推，直到所有人都出圈，由此产生一个出圈序列。或者求最后一个在座的小孩的编号。
 *
 * @Author wpcheng
 * @Create 2021-07-18-9:59
 * @Version 1.0
 */
public class Josephus {
    public static void main(String[] args) {

        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); //创建环形链表
        circleSingleLinkedList.addBoy(5); //添加节点
        circleSingleLinkedList.showBoy(); //显示环形链表
        /* 显示环形链表成功：
        * Boy节点的编号：	1
        * Boy节点的编号：	2
        * Boy节点的编号：	3
        * Boy节点的编号：	4
        * Boy节点的编号：	5
        * */

        System.out.println("=====================约瑟夫问题实现=====================");

        //测试约瑟夫问题实现  在五个小孩围成的圈中，从第3个小孩开始数，数到2的那个小孩出圈，以此类推
        circleSingleLinkedList.Josephus(3,2,5);
        /*
        * 出圈小孩的编号: 	4
        * 出圈小孩的编号: 	1
        * 出圈小孩的编号: 	3
        * 出圈小孩的编号: 	2
        * 最后留在圈中小孩编号为：5
        * */




    }
}

//创建单向环形链表
class CircleSingleLinkedList{
    //创建一个first节点，不赋予编号
    private Boy first = null;


    /**
     * 添加Boy节点，构建成一个环形链表
     * @param nums 要添加Boy节点的个数
     */
    public void addBoy(int nums){
        //nums数据校验
        if (nums < 1){
            System.out.println("nums的值不正确");
            return;
        }
        Boy curBoy = null;  //辅助变量
        //使用for循环添加Boy节点，创建环形链表
        for (int i = 1; i <= nums; i++) {
            //先根据编号，创建i个节点
            Boy boy = new Boy(i);
            //创建第一个Boy节点时
            if (i == 1){
                first = boy;
                first.setNext(first);//让first的next指向自己，构成环状
                curBoy = first; //先让curBoy指向first
            }else{
                curBoy.setNext(boy);// first节点指向boy节点
                boy.setNext(first); //将boy节点指向first节点，构成环状
                curBoy = boy;//curBoy节点后移
            }
        }
    }

    /**
     * 遍历当前环形链表
     */
    public void showBoy(){
        if (first == null){
            System.out.println("当前链表为空");
            return ;
        }
        Boy curBoy = first;
        while (true){
            System.out.println("Boy节点的编号：\t"+curBoy.getNo());
            if (curBoy.getNext() == first){
                break;//遍历完成
            }
            curBoy = curBoy.getNext();//curBoy节点后移
        }
    }

    /**
     * 约瑟夫问题（约瑟夫环）实现思路分析：
     * 1.创建一个辅助变量helper，在小孩报数前，helper指向环形链表的最后一个节点，first依旧指向头结点
     * 2.报数前的准备工作：把helper和first变量指向要报数的小孩，假设是第k个小孩报数，两个变量往后移动k-1次即可
     * 3.当小孩报完m个数后，让helper和first两个变量往后移动m-1次
     * 4.执行小孩出圈操作，first = first.next   helper.next = first
     * 5.被删除的Boy节点因为没有任何引用，会被回收
     *
     * @param startNo 表示从编号第几的的小孩开始数
     * @param countNum  表示数几下
     * @param nums  表示最初有多少个小孩，即环形链表中最先有多少个Boy节点·
     */
    public void Josephus(int startNo, int countNum, int nums){
        //先对数据进行校验
        if (first == null || startNo < 1 || startNo > nums){
            System.out.println("参数有误");
            return;
        }
        //定义辅助变量 用来小孩出圈（即删除Boy节点）
        Boy helper = first;
        //让helper变量指向环形链表的最后一个节点，即first前一个节点
        while(true){
            if (helper.getNext() == first){// helper变量以及指向环形链表的最后一个节点
                break;
            }
            helper = helper.getNext();//helper后移
        }
        //让first变量指向要报数的Boy节点，同时helper变量还是指向first前一个节点
        for (int j = 0;j< startNo-1; j++){
            first = first.getNext();
            helper = helper.getNext();
        }
        //实现报数操作,当小孩报数时，first和helper变量都往后移 countNum-1 次
        while(true){
            if (helper == first){ //当圈中只有一个小孩时
                break;
            }
            //first和helper变量都往后移 countNum-1 次
            for (int j =0; j< countNum-1; j++){
                first = first.getNext();
                helper = helper.getNext();
            }
            //for循环后的first变量正好就指向要出圈的Boy节点
            System.out.println("出圈小孩的编号: \t"+ first.getNo());
            //指向Boy节点出圈操作，及删除当first指向的节点
            first = first.getNext();
            helper.setNext(first);//让helper的下一个节点指向first
        }

        System.out.println("最后留在圈中小孩编号为："+first.getNo());
    }




}





//创建一个Boy类，表示一个节点
class Boy{
    private int no; //编号
    private Boy next;  //指向下一个节点，默认为null

    public Boy (int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

//    @Override
//    public String toString() {
//        return "Boy{" +
//                "no=" + no +
//                ", next=" + next +
//                '}';
//    }
}
